package main

import "fmt"

func main() {
	//matrix:=[][]int{
	//	{1,3,5,7},
	//	{10,11,16,20},
	//	{23,30,34,6},
	//}
	//target:=4
	matrix := [][]int{
		{1, 3, 5, 7},
		{10, 11, 16, 20},
		{23, 30, 34, 50},
	}
	target := 30
	fmt.Println(searchMatrix(matrix, target))
}

func searchMatrix(matrix [][]int, target int) bool {
	//首先根据target判断行
	targetColumn := 0
	for column := 0; column < len(matrix); column++ {
		if matrix[column][0] > target {
			targetColumn = column - 1
			break
		} else if matrix[column][0] == target {
			//若有相等的数据直接返回
			return true
		}
		//若最后一行数据还未找到
		if column == len(matrix)-1 {
			targetColumn = column
		}
	}
	if targetColumn < 0 {
		return false
	}

	//再根据行判断是否有该数字
	for row := 0; row < len(matrix[targetColumn]); row++ {
		if target == matrix[targetColumn][row] {
			return true
		}
	}
	return false
}
